package leetcode_121_140;

import utils.TreeNode;

import java.util.List;

public class maxPathSum_124 {
    /**
     * 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。
     * 同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
     * 路径和 是路径中各节点值的总和。
     * 给你一个二叉树的根节点 root ，返回其 最大路径和
     */
    public int maxPathSum(TreeNode root) {
        /**
         * 想法是从下往上递归
         * 计算每一个节点，以它为根的二叉树中包括这个根节点的路径中每个节点只选择一个孩子节点进行连接的路径的最大值
         * 同时计算每一个节点可以同时连接左右孩子节点的情况，也就是是单独存在的无需连接上层节点的路径
         * 需要考虑全为负数的情况，此时只需要找到最大的单个节点即可
         * 1ms
         * 自己解决的，不到40分钟
         * 难道说我真是？
         */
        int sum=function(root);
        if(flag==true)
            return maxSum1;
       return Math.max(sum,maxSum1);
    }
    int maxSum1=Integer.MIN_VALUE;//最大的单独存在的无需连接上层节点的路径或节点

    boolean flag=true;  //是否全为负数
    /**
     * @return 返回包括 root 节点的一条最大路径，路径中每个节点都只能连接一个孩子节点
     */
    public int function(TreeNode root){
        if(root==null)
            return 0;

        if(root.val>=0)
            flag=false;

        //计算左右子树的贡献值
        int left=function(root.left);
        int right=function(root.right);

        maxSum1=Math.max(left+root.val+right,maxSum1);  //同时连接左右孩子节点的贡献值值与之前的最大单独路径比较，保存较大的
        int maxSum2=root.val+Math.max(left,right);  //只选择一个孩子节点
        return Math.max(maxSum2, 0); //如果小于0，则断开连接，不使用这部分，返回0即可
    }
}
